package leetcode_700;

/**
 *@author 周杨
 *MaximumSwap_670 給定一個數字 要求只能交换一次 输出最大结果
 *describe:用桶记录0-9出现的最高位 AC 100%
 *see:https://blog.csdn.net/huanghanqian/article/details/77870414
 *2018年10月5日 下午1:19:52
 */
public class MaximumSwap_670 {

	public int maximumSwap(int num) {
		char[] digits = Integer.toString(num).toCharArray();

		int[] buckets = new int[10];
		for (int i = 0; i < digits.length; i++) {// 储存1-9最先出现
			buckets[digits[i] - '0'] = i;
		}

		for (int i = 0; i < digits.length; i++) { // 从最高位开始
			for (int k = 9; k > digits[i] - '0'; k--) { // k需要比数字digits[i]大
				if (buckets[k] > i) { // 如果k的位置在i后面
					char tmp = digits[i];
					digits[i] = digits[buckets[k]];
					digits[buckets[k]] = tmp;
					return Integer.valueOf(new String(digits));
				}
			}
		}

		return num;
	}

}
